package com.startrek.ch02;

import java.util.Stack;

public class SinglyLinkedListReverse {

    /*
    这个方法会改变原链表结构
    1. Initialize three pointers prev as NULL, curr as head and next as NULL.
    2. Iterate through the linked list. In loop, do following.
        // Before changing next of current,
        // store next node
        next = curr->next
        // Now change next of current
        // This is where actual reversing happens
        curr->next = prev
        // Move prev and curr one step forward
        prev = curr
        curr = next
     */
    public Node reverseLinkedList(Node head) {
        if (head == null) {
            throw new IllegalArgumentException("Head must not be null");
        }

        Node currNode = head;
        Node prevNode = null;
        Node nextNode = null;
        while (currNode != null) {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }
        return prevNode;
    }

    /* 这个方法只是打印结果，不会改变原结构 */
    public void reverseLinkedList2(Node head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

class Node {
    int val;
    Node next;
}
